#include <iostream>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 };
 
class Solution {
public:

    // pair<int, bool> dfs(TreeNode* pRoot)
    // {
    //     if(pRoot == nullptr) return {0, true};

    //     pair<int, bool> leftH = dfs(pRoot->left);
    //     pair<int, bool> rightH = dfs(pRoot->right);

    //     if(abs(leftH.first - rightH.first) <= 1 && leftH.second && rightH.second)
    //         return {max(leftH.first, rightH.first) + 1, true};
    //     else
    //         return {max(leftH.first, rightH.first) + 1, false};
    // }

    bool IsBalanced_Solution(TreeNode* pRoot)
    {
        return dfs(pRoot) == -1 ? false : true;
    }

    int dfs(TreeNode* root)
    {
        if (root == nullptr) return 0;

        int left = dfs(root->left);
        if (left == -1) return -1;
        int right = dfs(root->right);
        if (right == -1) return -1;

        return abs(left - right) <= 1 ? max(left, right) + 1 : -1;
    }
};

int main()
{
    return 0;
}